#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//memset()
#include <assert.h>//assert()

#define max_size 100

typedef int datatype;

typedef struct SeqList//静态顺序表
{
	datatype a[max_size];//定数组长
	int size;//有效数据个数
}SL;

//静态顺序表初始化
void seqlistint(SL* sl)
{
	memset(sl->a, 0, sizeof(datatype) * max_size);//初始化函数，将某一块的值全部设为指定的值。第一个：要填充的内存。第二：要被设为的值。第三：要被设置该值的字符数，单位为字节。
	sl->size = 0;//现在一个数据都没有，所以现在这个为0；
}

void SeqListPushBack(SL* sl, datatype x)//静态顺序表尾插
{
	if (sl->size >= max_size)
	{
		printf("seqlist is full\n");
		return;
	}

	sl->a[sl->size] = x;
	sl->size++;
}

typedef struct SeqList//动态顺序表
{
	datatype* a;
	int size;    //有效数据的个数
	int capacity;//容量
}SL;
//动态顺序表初始化
void seqlistint(SL* sl)
{
	sl->a = NULL;
	sl->size = 0;
	sl->capacity = 0;
}

void SeqListCheckCapacity(SL* sl)//检测内存是否足够
{
	int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
	if (sl->size == sl->capacity)//满了要扩容
	{
		datatype* tmp = (datatype*)realloc(sl->a, newcapacity * sizeof(datatype));
		if (tmp == NULL)//扩容失败
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			sl->a = tmp;
			sl->capacity = newcapacity;
		}
	}
}

void SeqListDestory(SL* sl)//释放空间,最后的时候释放，否则可能会导致内存泄露
{
	free(sl->a);
	sl->a = NULL;
	sl->capacity = sl->size = 0;
}
void SeqListPushBack(SL* sl, datatype x)//动态顺序表尾插
{
	SeqListCheckCapacity(sl);//检测内存，一次封装，可处处使用
	sl->a[sl->size] = x;
	sl->size++;
}

void SeqListPushFront(SL* sl, datatype x)//头插
{
	SeqListCheckCapacity(sl);
	int end = sl->size - 1;
	while (end >= 0)//顺序表从后向后挪
	{
		sl->a[end + 1] = sl->a[end];
		--end;
	}
	sl->a[0] = x;
	sl->size++;
}

void SeqListPopBack(SL* sl)//尾删
{
	assert(sl->size > 0);//断言，大于0继续，小于等于零终止程序运行
	sl->size--;
}

void SeqListfPopFront(SL* sl)//头删
{
	assert(sl->size > 0);
	int start = 1;
	while (start < sl->size)
	{
		sl->a[start - 1] = sl->a[start];//从后往前放
		++start;
	}
	sl->size--;
}

void SeqListInsert(SL* sl, int pos, datatype x)//在中间插入数据 pos数组下标位置
{
	assert(pos < sl->size);
	SeqListCheckCapacity(sl);
	int end = sl->size - 1;
	while (end >= pos)
	{
		sl->a[end + 1] = sl->a[end];
		--end;
	}
	sl->a[pos] = x;
	sl->size++;
}

void SeqListErase(SL* sl, int pos)//任意地方删除
{
	assert(pos < sl->size);
	int start = pos + 1;
	while (start < sl->size)
	{
		sl->a[start - 1] = sl->a[start];
		++start;
	}
	sl->size--;
}

int SeqListFind(SL* sl, datatype x)//查找
{
	for (int i = 0; i < sl->size; ++i)
	{
		if (sl->a[i] == x)
		{
			return i;//返回数组下标
		}
	}
	return -1;//没有找到返回-1，因为i是大于等于0的数
}

void SeqListModity(SL* sl,int pos, datatype x)//修改
{
	assert(pos < sl->size);
	sl->a[pos] = x;
}
void seqlistprint(SL* sl)//打印输出顺序表
{
	for (int i = 0; i < sl->size; ++i)
	{
		printf("%d", sl->a[i]);
	}
	printf("\n");
}



void testseqlist()
{
	SL sl;
	seqlistint(&sl);
	SeqListPushBack(&sl, 1);
}
